package com.cn.algorithm02.class05;

import com.cn.algorithm02.class01.CodeUtil;
import com.sun.org.apache.bcel.internal.classfile.Code;

/***
 * @author: hels
 * @description: 遍历数组，求元素左边比当前元素小的数的和累加
 * {1,2}   sum=1
 * {1,2,3}   sum=1 + (1+2) = 4
 * **/
public class C02_SmallSum {
    public static void main(String[] args) {
        int[] arr = CodeUtil.generatorArray(10, 8, true);
        System.out.println(process(arr, 0, arr.length - 1));
        CodeUtil.printArray(arr);
    }

    public static int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }

        int mid = L + ((R - L)>>1);
        return process(arr, L, mid) + process(arr, mid+1, R) + merge(arr, L, mid, R);
    }

    public static int merge(int[] arr, int L, int mid, int R) {
        int[] sortArr = new int[R - L +1];
        int index = 0;// sortArr辅助下标
        int p1 = L,p2 = mid+1;
        int ans = 0;

        while (p1 <= mid && p2 <= R) {
            ans += arr[p1] < arr[p2] ? (R - p2 + 1)*arr[p1] : 0;
            sortArr[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            sortArr[index++] = arr[p1++];
        }
        while (p2 <= R) {
            sortArr[index++] = arr[p2++];
        }
        for (int i = 0; i < sortArr.length; i++) {
            arr[L++] = sortArr[i];
        }
        return ans;
    }
}